package com.lw.leetcode.bit.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 957. N 天后的牢房
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/28 11:28
 */
public class PrisonAfterNDays {


    public static void main(String[] args) {
        PrisonAfterNDays test = new PrisonAfterNDays();

        // [0,0,1,1,0,0,0,0]
//        int[] arr = {0, 1, 0, 1, 1, 0, 0, 1};
//        int n = 7;

        //  [0,0,1,1,1,1,1,0]
        int[] arr = {1, 0, 0, 1, 0, 0, 1, 0};
        int n = 1000000000;

        int[] ints = test.prisonAfterNDays(arr, n);
        System.out.println(Arrays.toString(ints));
    }

    public int[] prisonAfterNDays(int[] cells, int n) {
        int item = 0;
        for (int cell : cells) {
            item = (item << 1) + cell;
        }
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> flag = new HashMap<>();
        map.put(0, item);
        flag.put(item, 0);
        int i = 1;
        int t = 0;
        for (; i < 1000; i++) {
            item = ((~(item ^ (item << 2))) >> 1) & 0X7E;
            if (flag.containsKey(item)) {
                t = flag.get(item);
                break;
            }
            flag.put(item, i);
            map.put(i, item);
        }
        if (n < i) {
            item = map.get(n);
        } else {
            item = map.get((n - t) % (i - t) + t);
        }
        for (int k = 0; k < 8; k++) {
            cells[7 - k] = item & 1;
            item >>= 1;
        }
        return cells;
    }
}
